package leetcode101.search_problem.dfs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code7
 * @Description 51. N-Queens
 * The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
 *
 * Given an integer n, return all distinct solutions to the n-queens puzzle.
 *
 * Each solution contains a distinct board configuration of the n-queens' placement,
 * where 'Q' and '.' both indicate a queen and an empty space, respectively.
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-02 11:03
 */
public class Code7 {
    public static void main(String[] args) {

    }

    public static List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        List<List<String>> res = new ArrayList<>();
        initial(board);
        dfs(res, board, 0);
        return res;
    }

    public static void dfs(List<List<String>> res, char[][] board, int rowIndex) {
        if (rowIndex == board.length) {
            res.add(generate(board));
            return;
        }

        for (int colIndex = 0; colIndex < board.length; colIndex++) {
            if (isValid(board, rowIndex, colIndex)) {
                board[rowIndex][colIndex] = 'Q';
                dfs(res, board, rowIndex + 1);
                board[rowIndex][colIndex] = '.';
            }
        }
    }

    public static boolean isValid(char[][] board, int rowIndex, int colIndex) {
        /*
        判断之前行是否在某一列上有'Q'了
         */
        for (int i = 0; i < rowIndex; i++) {
            if (board[i][colIndex] == 'Q') {
                return false;
            }
        }

        /*
        判断左斜线是否有'Q'
         */
        for (int i = rowIndex - 1, j = colIndex - 1; i > -1 && j > -1; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        /*
        判断右上斜线是否有'Q'
         */
        for (int i = rowIndex - 1, j = colIndex + 1; i > -1 && j < board[i].length ; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }

    public static List<String> generate(char[][] board) {
        List<String> temp = new ArrayList<>();
        StringBuilder sb;
        for (char[] chars : board) {
            sb = new StringBuilder();
            for (char aChar : chars) {
                sb.append(aChar);
            }
            temp.add(sb.toString());
        }
        return temp;
    }

    public static void initial(char[][] board) {
        for (char[] chars : board) {
            Arrays.fill(chars, '.');
        }
    }
}
